/*
 * @lc app=leetcode.cn id=35 lang=java
 *
 * [35] 搜索插入位置
 */

// @lc code=start
class Solution {
    public int searchInsert(int[] nums, int target) {
        //边界处理,避免多余循环
        if(target<nums[0]){
            return 0;
        }
        if(target>nums[nums.length-1]){
            return nums.length;
        }
        //正常情况
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(target==nums[middle]){
                return middle;
            }else if(target<nums[middle]){
                right=middle-1;
            }else if(target>nums[middle]){
                left=middle+1;
            }
        }
        //这里需要理解一下为什么返回left即可？
        // 最后target一定在两个数之间，因此，考虑这两个数在上面未跳出出循环时，
        //有right-left=1，则middle位于left，此时比较一次后，left=middle+1,也就是插入的正确位置
        return left;
    }
}
// @lc code=end

